home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _skiplist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  7.2 KB  |  348 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _skiplist.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. //------------------------------------------------------------------------------
  17. //
  18. //  skip lists 
  19. //
  20. //  doubly linked
  21. //
  22. //  S. Naeher (1992)
  23. //
  24. //------------------------------------------------------------------------------
  25.  
  26.  
  27. #include <LEDA/impl/skiplist.h>
  28.  
  29. #define NODE_SIZE(l) sizeof(skiplist_node)+l*sizeof(skiplist_node*)
  30.  
  31. #define NEW_NODE(p,l) p=(skiplist_item)allocate_bytes(NODE_SIZE(l));p->level=l;
  32.  
  33. #define NEW_NODE_0(p,l) p=(skiplist_item)malloc(NODE_SIZE(l));p->level=l;
  34.  
  35. #define FREE_NODE(p) deallocate_bytes(p,NODE_SIZE(p->level))
  36.  
  37. #define FREE_NODE_0(p) free(p)
  38.  
  39.  
  40. const int BitsInRandom      = 31;
  41. const int MaxNumberOfLevels = 32;
  42.  
  43. skiplist::skiplist(float p) 
  44. { prob = p;
  45.   randomBits = random(0,MAXINT-1);
  46.   randomsLeft = BitsInRandom;
  47.   level = 0;
  48.   count = 0;
  49.  
  50.   NEW_NODE_0(header,MaxNumberOfLevels);
  51.   NEW_NODE_0(STOP,-1);
  52.   STOP->backward = header;
  53.   STOP->pred = header;
  54.  
  55.   for(int i=0;i<MaxNumberOfLevels;i++) header->forward[i] = STOP;
  56.   header->backward = 0;
  57.   header->pred = 0;
  58.  
  59.  } 
  60.  
  61. skiplist::skiplist(const skiplist& L) 
  62. { prob = L.prob;
  63.   randomBits = random(0,MAXINT-1);
  64.   randomsLeft = BitsInRandom;
  65.   level = 0;
  66.   count = 0;
  67.  
  68.   NEW_NODE_0(header,MaxNumberOfLevels);
  69.   NEW_NODE_0(STOP,-1);
  70.   STOP->backward = header;
  71.   STOP->pred = header;
  72.  
  73.   for(int i=0;i<MaxNumberOfLevels;i++) header->forward[i] = STOP;
  74.   header->backward = 0;
  75.   header->pred = 0;
  76.  
  77.  
  78.   skiplist_item p = L.STOP->pred;
  79.   while (p!= L.header) 
  80.   { insert_at_item(header,p->key,p->inf);
  81.     L.copy_key(p->key);
  82.     L.copy_inf(p->inf);
  83.     p = p->pred;
  84.    }
  85.  } 
  86.  
  87.  
  88. skiplist& skiplist::operator=(const skiplist& L) 
  89. { clear();
  90.   skiplist_item p = L.STOP->pred;
  91.   while (p!= L.header) 
  92.   { insert_at_item(header,p->key,p->inf);
  93.     p = p->pred;
  94.    }
  95.   return *this;
  96.  } 
  97.  
  98. void skiplist::clear() 
  99. { register skiplist_item p,q;
  100.   p = header->forward[0];
  101.   while(p!=STOP)
  102.   { q = p->forward[0];
  103.     clear_key(p->key);
  104.     clear_inf(p->inf);
  105.     FREE_NODE(p);
  106.     p = q; 
  107.    }
  108.  level = 0;
  109.  for(int i=0;i<MaxNumberOfLevels;i++) header->forward[i] = STOP;
  110.  STOP->pred = header;
  111.  count = 0;
  112. }
  113.  
  114.  
  115.  
  116. skiplist::~skiplist() 
  117. { clear();
  118.   FREE_NODE_0(header);
  119.   FREE_NODE_0(STOP);
  120.  }
  121.  
  122.  
  123. int skiplist::randomLevel()
  124. {  register int level = 0;
  125.    register int b  = 0;
  126.  
  127.    if (prob==0.25)  
  128.       // while (random() < MAXINT/4) level++;
  129.       while (b==0)
  130.       { b = randomBits&3;    // read next two random bits
  131.         randomBits >>= 2;
  132.         randomsLeft -= 2;
  133.         if (b==0) level++;   // increase level with prob 0.25
  134.         if (randomsLeft < 2) 
  135.         { randomBits = random(0,MAXINT-1);
  136.           randomsLeft = BitsInRandom;
  137.          }
  138.        }
  139.    else            // user defined prob.
  140.      while (rrandom() < prob) level++;
  141.     
  142.    return level;
  143.  }
  144.  
  145.  
  146. skiplist_item skiplist::search(GenPtr key, int& l) const
  147. { register skiplist_item p = header;
  148.   register skiplist_item q;
  149.   register k,c=1;
  150.  
  151.   if (int_type())
  152.   { STOP->key = key;
  153.     for(k = level; k>=0; k--)
  154.     { q = p->forward[k];
  155.       while (long(key) > long(q->key)) 
  156.       { p = q;
  157.         q = p->forward[k];
  158.        }
  159.       if(key==q->key && q != STOP) break;
  160.      }
  161.    }
  162.   else
  163.   { for(k = level; k>=0; k--)
  164.     { q = p->forward[k];
  165.       while (k==q->level && (c=cmp(key,q->key)) > 0)
  166.       { p = q;
  167.         q = p->forward[k];
  168.        }
  169.       if(c==0) break;
  170.      }
  171.    }
  172.   l = k;
  173.   return q;
  174.  }
  175.  
  176.  
  177. skiplist_item skiplist::locate(GenPtr key) const
  178. { int k;
  179.   skiplist_item q = search(key,k);
  180.   return (q==STOP) ? q->pred : q;
  181.  }
  182.  
  183.  
  184. skiplist_item skiplist::locate_succ(GenPtr key) const
  185. { int k;
  186.   skiplist_item q = search(key,k);
  187.   if (q==header) return min();
  188.   if (cmp(key,q->key)!=0) q = q->forward[0];
  189.   return (q==STOP) ? 0 : q;
  190.  }
  191.  
  192. skiplist_item skiplist::locate_pred(GenPtr key) const
  193. { int k;
  194.   skiplist_item q = search(key,k);
  195.   if (q==STOP) return max();
  196.   if (cmp(key,q->key)!=0) q = q->pred;
  197.   return (q==header) ? 0 : q;
  198.  }
  199.  
  200.  
  201.  
  202.  
  203. skiplist_item skiplist::lookup(GenPtr key) const
  204. { int k;
  205.   skiplist_item q = search(key,k);
  206.   return (k<0) ? 0 : q;
  207.  }
  208.  
  209.  
  210. void skiplist::insert_item_at_item(skiplist_item q, skiplist_item p)
  211. { 
  212.   // insert item q immediately after item p
  213.  
  214.   register skiplist_item x;
  215.   register int k;
  216.   q->pred = p;
  217.   p->forward[0]->pred = q;
  218.   for(k=0; k<=q->level; k++)
  219.   { while (k > p->level) p = p->backward;
  220.     x = p->forward[k];
  221.     q->forward[k] = x;
  222.     p->forward[k] = q;
  223.     if (x->level == k) x->backward = q;
  224.    }
  225.    q->backward = p;
  226.  }
  227.  
  228.  
  229. skiplist_item skiplist::insert_at_item(skiplist_item p, GenPtr key, GenPtr inf)
  230. { register skiplist_item q;
  231.   register int k;
  232.  
  233.   if (p != header)
  234.   { int c = cmp(key,p->key);
  235.  
  236.     if (c == 0)
  237.     { clear_inf(p->inf);
  238.       copy_inf(inf);
  239.       p->inf = inf;
  240.       return p;
  241.      }
  242.  
  243.     if (c<0) p = p->pred;
  244.  
  245. /*
  246.      if (p!=min() && cmp(key,p->pred->key) <= 0)
  247.      {  cout << "wrong position for "; print_key(key);
  248.         newline;
  249.         cout << " pos = "; print_key(p->key);
  250.         newline;
  251.         cout << " pred = "; print_key(p->pred->key);
  252.         newline;
  253.         error_handler(1,"skiplist::insert_at : wrong position "); 
  254.       }
  255. */
  256.    }
  257.  
  258.    k = randomLevel();
  259.    if (k>level) k = ++level;
  260.  
  261.    NEW_NODE(q,k);
  262.    copy_key(key);
  263.    copy_inf(inf);
  264.    q->key = key;
  265.    q->inf = inf;
  266.    count++;
  267.  
  268.    insert_item_at_item(q,p);
  269.  
  270.    return q;
  271.  }
  272.  
  273.  
  274. void skiplist::remove_item(skiplist_item q)
  275. { register int k;
  276.   register skiplist_item p = q->backward;
  277.   register skiplist_item x;
  278.  
  279.   for(k=q->level; k>=0; k--)
  280.   { while (p->forward[k] != q) p = p->forward[k];
  281.     x = q->forward[k];
  282.     p->forward[k] = x;
  283.     if (x->level==k) x->backward = p;
  284.    }
  285.   x->pred = p;
  286. }
  287.  
  288.  
  289. void skiplist::del_item(skiplist_item q)
  290. { remove_item(q);
  291.   clear_key(q->key);
  292.   clear_inf(q->inf);
  293.   FREE_NODE(q);
  294.   while(header->forward[level] == STOP && level > 0 ) level--;
  295.   count --;
  296. }
  297.  
  298. skiplist_item skiplist::insert(GenPtr key, GenPtr inf)
  299. { int k;
  300.   skiplist_item p = search(key,k);
  301.   if (p==STOP) p = p->pred;
  302.   return insert_at_item(p,key,inf);
  303.  }
  304.  
  305. void skiplist::del(GenPtr key)
  306. { int k;
  307.   skiplist_item q = search(key,k);
  308.   if (k>=0) del_item(q);
  309.  }
  310.  
  311.  
  312. void skiplist::reverse_items(skiplist_item p, skiplist_item q)
  313. { skiplist_item r;
  314.   while (p!=q)
  315.   { r = p;
  316.     p = p->forward[0];
  317.     remove_item(r);
  318.     insert_item_at_item(r,q);
  319.    }
  320.  }
  321.  
  322. void skiplist::conc(skiplist&)
  323. { error_handler(1,"sorry, not implemented: skiplist::conc(skiplist)\n"); }
  324.  
  325. void skiplist::split_at_item(skiplist_item,skiplist&,skiplist&)
  326. { error_handler(1,"sorry, not implemented: skiplist::split_at_item\n"); }
  327.  
  328.  
  329. void skiplist::print()
  330. { skiplist_item p = header;
  331.   cout << "Level = " << level << "\n"; 
  332.   for(;;)
  333.   { cout << string("<%d>  ",p);
  334.     if (p != header && p != STOP)
  335.     { cout << "key = ";
  336.       print_key(p->key);
  337.      }
  338.     newline;
  339.     for(int k=p->level;k>=0;k--)
  340.        cout << string("forward[%d] = %8d\n", k,p->forward[k]);
  341.     cout << string("backward = %8d   pred = %8d\n",p->backward, p->pred);
  342.     if (p==STOP) break;
  343.     p = p->forward[0];
  344.     newline;
  345.    }
  346. }
  347.  
  348.